import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution90 {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> ans=new ArrayList<>();
        Map<Integer,Integer> map=new HashMap<>();
        for (int num : nums) {
            map.put(num,map.getOrDefault(num,0)+1);
        }
        dfs(new ArrayList<>(),ans,-10,map);
        return ans;
    }

    private void dfs(ArrayList<Integer> objects, List<List<Integer>> ans, int k, Map<Integer, Integer> map) {
        for (int i=k;i<=10;i++){
            if (map.containsKey(i)){
                for (int j=0;j<map.get(i);j++){
                    objects.add(i);
                    dfs(objects,ans,i+1,map);
                }
                for (int j=0;j<map.get(i);j++){
                    objects.remove(objects.size()-1);
                }
            }
        }
        ans.add(new ArrayList<>(objects));
    }

    public static void main(String[] args) {
        System.out.println(new Solution90().subsetsWithDup(new int[]{1,2,2}));
    }
}
